package ExpressFive;

//队列，双向不循环
public class MyQueue<T> {
    static class Node<T> {
        private final T data;
        private Node<T> next, pre;

        public Node(T data) {
            this.data = data;
        }

    }

    private int len;
    private Node<T> head, tail;

    public MyQueue() {
        len = 0;
        head = tail = null;
    }

    public void add(T data) {
        if (data != null) {
            if (head == null) {
                head = new Node<>(data);
                tail = head;
            } else {
                tail.next = new Node<>(data);
                tail.next.pre = tail;
                tail = tail.next;
            }
            len++;
        }
    }

    public T remove(int index) {
        if (index < 0 || index >= len) {
            return null;
        }
        if(head==null)
            return null;
        Node<T> pt = head;
        while (index-- != 0) {
            pt = pt.next;
        }
        if (pt == head) {
            if (pt == tail) {
                //仅存一个
                head = tail = null;
            } else {
                head = pt.next;
                head.pre = null;
            }
        }
        else if(pt==tail){
            tail=pt.pre;
            tail.next=null;
        }
        else {
            pt.next.pre = pt.pre;
            pt.pre.next = pt.next;
        }
        len--;
        pt.next = pt.pre = null;
        return pt.data;
    }

    public T remove(T data) {
        if (data != null) {
            if(head==null){
                return null;
            }
            Node<T> pt = head;
            while (pt != null && pt.data != data) {
                pt = pt.next;
            }
            if (pt != null) {
                if (pt == head) {
                    if (pt == tail) {
                        head = tail = null;
                    } else {
                        head = head.next;
                        head.pre = null;
                    }
                }
                else if(pt==tail){
                    tail=pt.pre;
                    tail.next=null;
                }
                else {
                    pt.next.pre = pt.pre;
                    pt.pre.next = pt.next;
                }
                len--;
                pt.next = pt.pre = null;
                return pt.data;
            }
        }
        return null;

    }
    public T removeHead() {
        if (head != null) {
            Node<T> pt = head;
            if (head == tail) {
                head = tail = null;
            } else {
                head = head.next;
                head.pre = null;
            }
            len--;
            pt.next = pt.pre = null;
            return pt.data;
        }
        return null;
    }
    public T removeTail(){
        if(tail!=null){
            Node<T>pt=tail;
            if(tail==head){
                tail=head=null;
            }
            else{
                tail=tail.pre;
                tail.next=null;
            }
            len--;
            pt.next=pt.pre=null;
            return pt.data;
        }
        return null;
    }

    public T get(int index) {
        if (index < 0 || index >= len) {
            return null;
        }
        Node<T> pt = head;
        while (index-- != 0) {
            pt = pt.next;
        }
        return pt.data;
    }

    public T getHead() {
        if (head != null)
            return head.data;
        return null;
    }

    public T getTail() {
        if (tail != null)
            return tail.data;
        return null;
    }

    public int size() {
        return len;
    }

    public static void main(String[] args) {
        MyQueue<Integer> queue = new MyQueue<>();
        queue.add(1);
        queue.add(2);
        queue.add(3);
        queue.add(4);

        for (int i = 0; i < queue.size(); i++) {
            System.out.println(queue.get(i));
        }
        System.out.println("--------------");
        queue.remove(0);
        for (int i = 0; i < queue.size(); i++) {
            System.out.println(queue.get(i));
        }
        System.out.println("--------------");
        queue.remove(4);
        for (int i = 0; i < queue.size(); i++) {
            System.out.println(queue.get(i));
        }
        System.out.println("--------------");
        for (int i = 0; i < queue.size(); i++) {
            queue.remove(0);
        }
        queue.remove(0);
        System.out.println(queue.size());
    }
}
